//
// Created by 11510 on 2024/6/24.
//
#include <iostream>
#include <vector>
#include <functional>

template<typename T, typename Compare = std::less<T>>
class MyQsort {
public:
    MyQsort(T *arr, size_t size, Compare com = Compare())
            : _vec(arr, arr + size), _compare(com) {}

    void quick(int left, int right) {
        if (left < right) {
            int pivotIndex = partition(left, right);
            quick(left, pivotIndex - 1);
            quick(pivotIndex + 1, right);
        }
    }

    void print() {
        for (const auto& elem : _vec) {
            std::cout << elem << " ";
        }
        std::cout << std::endl;
    }

private:
    std::vector<T> _vec;
    Compare _compare;

    int partition(int left, int right) {
        T pivot = _vec[right];
        int i = left - 1;
        for (int j = left; j < right; ++j) {
            if (_compare(_vec[j], pivot)) {
                ++i;
                std::swap(_vec[i], _vec[j]);
            }
        }
        std::swap(_vec[i + 1], _vec[right]);
        return i + 1;
    }
};

// 示例使用
int main() {
    int arr[] = {3, 6, 8, 10, 1, 2, 1};
    size_t size = sizeof(arr) / sizeof(arr[0]);

    MyQsort<int> sorter(arr, size);
    sorter.quick(0, size - 1);
    sorter.print();

    return 0;
}
